package com.dyz.leetcode._13_binaryTree;

import com.dyz.leetcode.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

public class _100_isSameTree {
    //DFS
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null&& q==null){return true;}
        if(p==null || q==null){return false;}
        if(p.val!=q.val){return false;}
        boolean leftSameTree = isSameTree(p.left, q.left);
        boolean rightSameTree = isSameTree(p.right, q.right);
        return leftSameTree && rightSameTree;
    }
    //BFS
    public boolean isSameTree1(TreeNode p, TreeNode q) {
        if(p==null&& q==null){return true;}
        if(p==null || q==null){return false;}
        Queue<TreeNode> queue1 = new LinkedList<>();
        Queue<TreeNode> queue2 = new LinkedList<>();
        queue1.add(p);
        queue2.add(q);
        while (!queue1.isEmpty() && !queue2.isEmpty()){
            TreeNode nodeP  = queue1.poll();
            TreeNode nodeQ = queue2.poll();
            if(nodeP.val!=nodeQ.val){
                return false;
            }
            TreeNode left1 = nodeP.left;
            TreeNode left2 = nodeQ.left;
            if(left1==null ^ left2==null){return false;}

            TreeNode right1 = nodeP.right;
            TreeNode right2 = nodeQ.right;
            if(right1==null ^ right2==null){return false;}

            if (left1 != null) {
                queue1.offer(left1);
            }
            if (right1 != null) {
                queue1.offer(right1);
            }
            if (left2 != null) {
                queue2.offer(left2);
            }
            if (right2 != null) {
                queue2.offer(right2);
            }
         }
        return queue1.isEmpty() && queue2.isEmpty();

    }

}
